package const_prop;

import java.util.HashSet;

import flow_graph.AssemFlowGraph;
import graph.Node;
import temp.Temp;
import util.List;
import assem.Instr;

public class ConstantPropagation 
{

	// contem a arvore de instrucoes 
	private AssemFlowGraph      _cfg;
	private List<Instr>         _instrs;
	private ReachingDefinitions _rd;

	public ConstantPropagation(List<Instr> instrs)
	{
		//Reaching Definitions usa o grafo
		_cfg = new AssemFlowGraph(instrs);
		
		//Reaching Definitions vai calcular o in e o out de cada noh
		_rd = new ReachingDefinitions(_cfg);
		
		//initializa a variavel de retorno com null
		_instrs = null;
		
		calculaCP();		
	}

	private void calculaCP()
	{
	
		/**
		 * Percorre todos os nohs do grafo e verifica onde pode substituir por constantes
		 */
		for( List<Node> nohs = _cfg.nodes(); nohs != null ; nohs = nohs.tail)
		{
			Node noh = nohs.head;
		
			/**
			 * Dado o noh, recupera todos os temps que ele usa e verifica se
			 * algum temp pode ser substituido
			 * Necessita guardar o indice do temp  
			 */
			int ind_temp_usado = 0; 
			for(List<Temp> temp_usados = _cfg.use(noh) ; temp_usados != null ; temp_usados = temp_usados.tail)
			{
				Temp temp_usado = temp_usados.head;
				
				// Recupera todos os nohs em que o temp_usado eh definido
				HashSet<Node> nohs_def_temp_usado = _rd.getDefs().get(temp_usado);
				// Recupera a lista de definicoes na entrada do noh atual
				HashSet<Node> in_noh_atual = _rd.getIn().get(noh);

				if (nohs_def_temp_usado != null)
				{
					/**
					 * Verifica se das definicoes (nohs) que alcancam o 'noh'
					 * existe somente uma definicao de 'temp_usado' e se
					 * esta definicao  eh do tipo 'mov  temp_usado, CONSTANTE'
					 * retorna true se achou somente um 
					 * falso senao
					 */
					StringBuilder cte = new StringBuilder("");
					if (fazTroca(nohs_def_temp_usado, in_noh_atual, cte) == true)
					{
						// substitui no assem de sX para o valor da constante
						_cfg.instr(noh).assem = _cfg.instr(noh).assem.replace(" `s" + ind_temp_usado, " DWORD"+cte);
					}
				}				
				ind_temp_usado++;
			}
			/* insere uma instrucao na lista de instrucoes 
			 * devido a classe List, foi necessario inserir em ordem reversa
			 */
			_instrs = new List<Instr> (_cfg.instr(noh), _instrs);
		}
		/**
		 * gera a lista de instrucoes na ordem correta
		 */
		List<Instr> lista_temp = _instrs;
		for (_instrs = null ; lista_temp != null; lista_temp = lista_temp.tail)
		{
			_instrs = new List<Instr> (lista_temp.head, _instrs);
		}
	}
		
	private boolean fazTroca(HashSet<Node> defs, HashSet<Node> in, StringBuilder cte)
	{
		// retorna true se precisa trocar o temp por uma cte
		boolean troca = false;
		
		//para cada noh que define um temp
		for (Node def : defs)
		{
			/**
			 * se este noh alcanca o noh de verificacao, 
			 * ou seja, se o noh de def estah no in do noh de referencia
			 * e este noh de def eh do tipo mov
			 * e o noh de definicao nao usa qquer outro temporario (ou seja, usa uma constante)
			 */
			if (in.contains(def) && 
			    ((_cfg.instr(def).assem.split(" "))[0]).equals("mov") == true && 
			    _cfg.use(def) == null )
			{
				/**
				 * jah havia achado uma outra definicao deste noh
				 * logo ele nao pode ser usado
				 */
				if (troca == true)
				{
					troca = false;
					/* sai do loop */
					break;
				}
				else
				{
					// deve fazer a troca
					troca = true;
					// recupera string do assembly
					String instrucao = _cfg.instr(def).assem;
					//recupera constante
					cte.append((instrucao.split(","))[1]);
				}
			}
		}
		return troca;
	}

	public List<Instr> getInstrs()
	{
		return _instrs;
	}

}
